import java.util.ArrayList;
import java.util.List;

public class GraphByNode {
    static class Node{
        public char src;
        public char dest;
        public int weight;
        public Node next;

        public Node(char src, char dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }

    public char[] arrayV;
    public List<Node> edgeList;
    public boolean isDirect;

    public GraphByNode(int size, boolean isDirect){
        this.arrayV = new char[size];

        this.edgeList = new ArrayList<>();
        for(int i = 0; i < size; i++){
            this.edgeList.add(null);
        }

        this.isDirect = isDirect;
    }

    // 初始化顶点数组
    public void initArrayV(char[] array){
        int n = this.arrayV.length;
        for(int i = 0; i < n; i++){
            this.arrayV[i] = array[i];
        }
    }

    public void addEdge(char srcV, char destV, int weight){
        addEdgeChild(srcV, destV, weight);

        if(!isDirect){
            addEdgeChild(destV, srcV, weight);
        }
    }

    private void addEdgeChild(char srcV, char destV, int weight){
        int src = getIndexOfV(srcV);
        int dest = getIndexOfV(destV);

        Node cur = edgeList.get(src);
        while(cur != null){
            if(cur.dest == destV){
                return;
            }
            cur = cur.next;
        }
        Node node = new Node(srcV, destV, weight);
        // 头插法
        node.next = edgeList.get(src);
        edgeList.set(src, node);
    }

    private int getIndexOfV(int v){
        int n = this.arrayV.length;
        for(int i = 0; i < n; i++){
            if(this.arrayV[i] == v){
                return i;
            }
        }
        return -1;
    }

    // 获取顶点的度
    public int getDevOfV(char v){
        int index = getIndexOfV(v);
        int count = 0;

        Node cur = edgeList.get(index);
        while(cur != null){
            count++;
            cur = cur.next;
        }

        // 如果是有向图，还需要统计入度
        int n = this.arrayV.length;
        if(isDirect){
            for(int i = 0; i < n; i++){
                if(i == index){
                    continue;
                }else{
                    Node tmp = edgeList.get(i);
                    while(tmp != null){
                        if(tmp.dest == v){
                            count++;
                        }
                        tmp = tmp.next;
                    }
                }
            }
        }

        return count;
    }

    public void printGraph(){
        int n = this.arrayV.length;
        for(int i = 0; i < n; i++){
            Node cur = edgeList.get(i);
            System.out.print(cur.src + ": ");
            while(cur != null){
                System.out.print(cur.dest);
                cur = cur.next;
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        char[] array = {'A', 'B', 'C', 'D'};
        GraphByNode graph = new GraphByNode(array.length, true);
        graph.initArrayV(array);

        graph.addEdge('A','B',1);
        graph.addEdge('A','D',1);
        graph.addEdge('B','A',1);
        graph.addEdge('B','C',1);
        graph.addEdge('C','B',1);
        graph.addEdge('C','D',1);
        graph.addEdge('D','A',1);
        graph.addEdge('D','C',1);

        graph.printGraph();

        System.out.println(graph.getDevOfV('A'));

        System.out.println();
    }
}
